#include <iostream>
#include <list>
#include <unordered_map>

using namespace std;

class LFUCache {
private:
    struct lfu_node {
        int frequency;
        list<tuple<int, int>> list;
        lfu_node(int frequency) : frequency(frequency) {}
    };
    list<lfu_node> lfu_list;
    unordered_map<int, tuple<list<lfu_node>::iterator, list<tuple<int, int>>::iterator>> lfu_map;
    int capacity;
    void frequency_add(list<lfu_node>::iterator& _lfu_node, list<tuple<int, int>>::iterator& _list_node, int& key, int& value) {
        list<lfu_node>::iterator _pre_lfu_node = _lfu_node; _pre_lfu_node--;
        if (_pre_lfu_node == lfu_list.end() || _pre_lfu_node->frequency != _lfu_node->frequency + 1) {
            lfu_list.insert(_lfu_node, lfu_node(_lfu_node->frequency + 1));
        }
        _pre_lfu_node = _lfu_node; _pre_lfu_node--;
        _pre_lfu_node->list.emplace_back(make_tuple(key, value));
        _lfu_node->list.erase(_list_node);
        if (_lfu_node->list.empty()) {
            lfu_list.erase(_lfu_node);
        }
        lfu_map[key] = {_pre_lfu_node, --(_pre_lfu_node->list.end())};
    }
public:
    LFUCache(int capacity) {
        this->capacity = capacity;
    }

    int get(int key) {
        if (capacity == 0 || lfu_map.find(key) == lfu_map.end()) {
            return -1;
        }
        tuple<list<lfu_node>::iterator, list<tuple<int, int>>::iterator>& lfu_store = lfu_map[key];
        int value = std::get<1>(*std::get<1>(lfu_store));
        frequency_add(std::get<0>(lfu_store), std::get<1>(lfu_store), key, value);
        return value;
    }

    void put(int key, int value) {
        if (capacity == 0) {
            return;
        }
        if (lfu_map.find(key) == lfu_map.end()) {
            if (lfu_map.size() == capacity) {
                int key = std::get<0>(lfu_list.rbegin()->list.front());
                lfu_list.rbegin()->list.pop_front();
                lfu_map.erase(key);
            }
            if (lfu_list.empty() || lfu_list.back().frequency != 1) {
                lfu_list.emplace_back(lfu_node(1));
            }
            lfu_list.back().list.emplace_back(make_tuple(key, value));
            lfu_map.insert({key, {--lfu_list.end(), --lfu_list.back().list.end()}});
        } else {
            tuple<list<lfu_node>::iterator, list<tuple<int, int>>::iterator>& lfu_store = lfu_map[key];
            frequency_add(std::get<0>(lfu_store), std::get<1>(lfu_store), key, value);
        }
    }
};


int main() {
    LFUCache lfuCache(2);
    lfuCache.put(1, 1);
    lfuCache.put(2, 2);
    int output = lfuCache.get(1);
    cout << output << endl;
    lfuCache.put(3, 3);    // 去除 key 2
    output = lfuCache.get(2);       // 返回 -1 (未找到key 2)
    cout << output << endl;
    output = lfuCache.get(3);       // 返回 3
    cout << output << endl;
    lfuCache.put(4, 4);    // 去除 key 1
    output = lfuCache.get(1);       // 返回 -1 (未找到 key 1)
    cout << output << endl;
    output = lfuCache.get(3);       // 返回 3
    cout << output << endl;
    output = lfuCache.get(4);       // 返回
    cout << output << endl;
}